from typing import *


class Solution:

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []

        def swap(x, y):
            nums[x], nums[y] = nums[y], nums[x]

        def f(id=0):
            if id == n:
                ans.append(nums.copy())
                return
            s = set()
            for i in range(id, n):
                v = nums[i]
                if v not in s:
                    s.add(v)
                    swap(id, i)
                    f(id + 1)
                    swap(id, i)

        f()
        return ans


class Solution:

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        nums.sort()
        v = [False] * n

        def f(id=0, arr: list = []):
            if id == n:
                ans.append(arr.copy())
                return
            for i in range(n):
                if v[i] or (nums[i] == nums[i - 1] and not v[i - 1]):
                    continue
                arr.append(nums[i])
                v[i] = True
                f(id + 1, arr)
                v[i] = False
                arr.pop()

        f()
        return ans


so = Solution()
print(so.permuteUnique(nums=[1, 1, 2]))
